#*************************************************************************
## This file contains a tree structure
#*************************************************************************

class Node:
    '''
    A node in a tree.
    @name:
    @children: a list of nodes
    @value:
    #func_map
    '''
    def __init__(self, name, children, value):
        self.name = name
        self.children = children[:]
        self.value = value
        self.func_map = {'GetSize':self._NodeCount, 'GetAVGN': self._NodeBranchCount}

##    def __del__(self):
##        '''
##        Delete a subtree
##        '''
####        print 'del node'
##        if(len(self.children) > 0):
##            for node in self.children:
##                del node
    #***********************************************************
    # Find i-th node and its parent
    #***********************************************************
    __indexnode = 0
    __idnode = None
    __idparent = None
    def __getitem__(self, index):
        '''
        call: tree[index]
        return: [node, parent]
        '''
        return self.FindNode(index)

    def FindNode(self, index):
        global __indexnode, __idnode, __idparent
        __indexnode = index
        self.__FindNode(self)
        return [__idnode, __idparent]
        
    def __FindNode(self, parent):
        '''
        Find index-th node and its parent (in preorder search)
        return: [node, parent]
        '''
        global __indexnode, __idnode, __idparent
        if (__indexnode > 0):           
            __indexnode = __indexnode - 1
            if (__indexnode == 0):
                __idnode = self
                __idparent = parent
            elif len(self.children) > 0:
                for child in self.children:
                    child.__FindNode(self)
        
    #*************************************************************
                    
    def Copy(self):
        '''
        Copy a subtree
        '''
        newNode = Node(self.name, [], self.value)
        for child in self.children:
            newNode.children.append(child.Copy())
        return newNode

    def GetHeight(self):
        '''
        Get the height of a subtree
        '''
        if (len(self.children) == 0):
            return 0
        else:
            maxh = 0
            for child in self.children:
                temp = child.GetHeight()
                if (temp > maxh):
                    maxh = temp
            return maxh + 1

    def Compare(self, node):
        '''
        Compare two subtree
        @node: a node to compare
        @return: True if equal. Otherwise, False
        '''
        if (node != None):
            t1 = self.name
            t2 = node.name
            if (self.name == node.name):
                n = len(self.children)
                if(len(node.children) != n):
                    return False
                elif n == 0:#do not have children
                    return True
                else:
                    for i in range(n):
                        if(self.children[i].Compare(node.children[i]) == False):
                            return False
                    return True
            else:
                return False
        else:
            return False

    

    def ToString(self):
        '''
        From a tree to string with brackets
        '''
        result = ''
        if (self.name == "ERC"):#for Ephemeral constants
            result += str(self.value)
        else:
            result += self.name
        n = len(self.children)
        if n > 0:
            result += "("
            for i in range(n):
                result += self.children[i].ToString()
                if i < n-1:
                    result += ", "
            result += ")"
        return result

    def Draw(self):
        '''
        Draw a tree
        '''
        self.__DrawTree(1)
        
    def __DrawTree(self, level):
        '''
        Draw a tree
        '''
        kIndentText = '|  '
        IndentText=''
        for n in range(1, level):
            IndentText += kIndentText
        if self.name == 'ERC': #for constants
            print IndentText + '+--[' + str(self.value) + ']'
        else:
            if len(self.children)>0:#function
                print IndentText + '+--' + self.name
                for child in self.children:
                    child.__DrawTree(level + 1)
            else: #var
                print IndentText + '+--[' + self.name + ']'

    #*************************************************************************
    # Travel a Tree in Preorder, Inorder and Postoder
    #*************************************************************************
        
##    func_map = {}

    def _preorder(self, func):
        '''
        @func: function pointer
        '''
##        global func_map
        if func != None and self.func_map.has_key(func):
            self.func_map[func]()
        for child in self.children:
            child._preorder(func)

    #*************************************************************************
    # Get the size of the tree
    #*************************************************************************
    _nodecount = 0
    _countleave = False
    def _NodeCount(self):
        global _nodecount, _countleave
    ##    print node.name
        _nodecount += 1
        if(_countleave==False and len(self.children) == 0):
            _nodecount -= 1
            
    def GetSize(self, countleave):
        global _nodecount, _countleave #, func_map
        _countleave = countleave
        _nodecount = 0
        self._preorder('GetSize')
        return _nodecount
    #*************************************************************************
    # Get the average branching of a tree
    #*************************************************************************
    _nodebranch = 0
    
    def _NodeBranchCount(self):
        global _nodebranch
        _nodebranch += len(self.children)
    
    def GetAVGNode(self):
        global _nodebranch
        if len(self.children) == 0:
            return 1.0
        size = self.GetSize(False)
        _nodebranch = 0
        self._preorder('GetAVGN')
        return float(_nodebranch)/size

